package Year22_Month06.day08;

import java.util.LinkedList;
import java.util.Queue;

public class 相同的树_迭代 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> q1 = new LinkedList<>();
        Queue<TreeNode> q2 = new LinkedList<>();
        //不为空才可以入栈
        if(p != null) q1.offer(p);
        if(q != null) q2.offer(q);
        while(!q1.isEmpty() && !q2.isEmpty()){
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            //如果当前两个节点都为null,就直接进入下次比较就行
            if(node1 == null && node2 == null) continue;
            //如果两个节点同时不为空并且值相等，就把左右子树入队列
            if(node1 != null && node2 != null && node1.val == node2.val){
                q1.offer(node1.left);
                q1.offer(node1.right);
                q2.offer(node2.left);
                q2.offer(node2.right);
            }else {
                return false;
            }
        }
        return q1.isEmpty() && q2.isEmpty();
    }
}
